import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;

/**
 * a utility provider that searches or traverses a graph
 * @author BaoTam
 *
 */
public class GraphSearch {

	/**
	 * Searches the graph represented by the given AdjacencyList starting at the
	 * given start vertex, for the given goal vertex, using the algorithm based
	 * on the given structure
	 * 
	 * @param start
	 *            the starting vertex, assume it's in al
	 * @param goal
	 *            the goal vertex, assume it's in al
	 * @param al
	 *            the AdjacencyList of the graph
	 * @param s
	 *            the Abstract Structure that determines which graph searching
	 *            algorithm will be used
	 * @return the path from start to goal found in the graph search, or null of
	 *         no such path is found
	 */
	public static Path search(Vertex start, Vertex goal, AdjacencyList al, Structure s) {
		if(start == null || al == null || s == null || goal == null || al.getAdjacencies(start) == null || al.getAdjacencies(goal) == null) {
			return null;
		}
		
		return explore(start,al,s).get(goal);
	}

	/**
	 * Explores the graph represented by the given AdjacencyList starting at the
	 * given start vertex, using the algorithm based on the given structure.
	 * This method should explore all vertices in the graph, and create a map of
	 * vertices to paths. If this map contains an Entry<Vertex, Path> = (v,p)
	 * that implies that p is the path to get from the given start vertex to the
	 * vertex v. If for a Vertex u, map.containsKey(u) returns false this
	 * implies that there is no path from start to u in the given graph.
	 * 
	 * @param start
	 *            the vertex to start exploring from
	 * @param al
	 *            the AdjacencyList representation of the graph
	 * @param s
	 *            the Structure that will determine which searching algorithm is
	 *            used
	 * @return a mapping of vertices to paths as described above
	 */
	public static Map<Vertex, Path> explore(Vertex start, AdjacencyList al,	Structure s) {
		if(start == null || al == null || s == null || al.getAdjacencies(start) == null) {
			return null;
		}
		
		s.add(new Path(start));
		Map<Vertex, Path> result = new HashMap<Vertex, Path>();

		while(!s.isEmpty()) {
			Path currPath = s.remove();
			Vertex currVertex = currPath.getLastVertex();
			//System.out.println("remove: " + currPath);
			
			if(result.containsKey(currVertex)) {
				continue;
			}
			
			result.put(currVertex, currPath);
			//System.out.println("put: " + result);
			//Add all paths to the adjacencies of the current vertex to the data structure
			SortedSet<Pair> adjSet = al.getAdjacencies(currVertex);
			for(Pair adjPair : adjSet) {
				if(result.containsKey(adjPair.getVertex())) {
					continue;
				}
				//System.out.println("-explore: " + new Path(currPair, currPath));
				s.add(new Path(adjPair, currPath));
				//ystem.out.println("--map: " + result);
			}
		}
		
		return result;
	}
}
